package cn.arnold.offer.bytedance;

//字符串最小循环节
public class ShortestSubstring {
    //    private static final int N = 1000000+10;
//    static char[] ch = new char[N];
//    static int[] next = new int[N];
    public static void main(String[] args) {


    }

    //求出一个字符数组的next数组
    static int[] next(char[] ch) {
        int[] next = new int[ch.length];
        next[0] = -1;
        next[1] = 0;
        int k;
        for (int i = 0; i < ch.length; i++) {
            k = next[i - 1];
            while (k != -1) {
                if (ch[i - 1] == ch[k]) {
                    next[i] = k + 1;
                    break;
                } else {
                    k = next[k];
                }
                next[i] = 0;
            }
        }
        return next;
    }
}
